package 数据结构设计高频题;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 全O(1)的数据结构
// 测试链接 : https://leetcode.cn/problems/all-oone-data-structure/
// 巧妙设计：Hash表+双向链表。桶的双向链表初始化就有两个节点，词频为0的头结点，词频为int最大值的尾结点
public class Code07_AllO1 {

    class AllOne {
        //创建桶，每个桶的区别就是统计词频cnt的值，相同词频的桶存放着HashSet集合，存储str字符串
        class Bucket{
            HashSet<String> strSet;
            Bucket next;
            Bucket last;
            int cnt;

            public Bucket(String str, int cnt) {
                this.strSet = new HashSet<>();
                strSet.add(str);
                this.cnt = cnt;
            }
        }

        // 插入新的桶，相当于双向链表
        public void insert(Bucket cur, Bucket purpose){
            cur.next.last = purpose;
            purpose.next = cur.next;
            cur.next = purpose;
            purpose.last = cur;
        }

        //删除桶
        public void remove(Bucket cur){
            cur.last.next = cur.next;
            cur.next.last = cur.last;
        }

        //head就是词频为0的桶。tail就是为int最大值的桶
        Bucket head;
        Bucket tail;
        //k值为：str，v值为：Bucket桶的地址
        HashMap<String, Bucket> map;

        //初始化，将两个作为基石的桶连接起来
        public AllOne() {
            head = new Bucket("", 0);
            tail = new Bucket("", Integer.MAX_VALUE);
            head.next = tail;
            tail.last = head;
            map = new HashMap<>();
        }

        public void inc(String key) {
            // 首先，查看map中是否有这条记录 ---》没有
            if(!map.containsKey(key)){
                // 查看桶的双向链表是否有词频值为1的节点
                if(head.next.cnt == 1){
                    map.put(key, head.next);
                    head.next.strSet.add(key);
                }else{
                    Bucket newBucket = new Bucket(key, 1);
                    map.put(key, newBucket);
                    insert(head, newBucket);
                }
            }else{
                // map中已经含有关于key的记录，取出其bucket节点
                Bucket bucket = map.get(key);
                // 判断当前bucket节点的词频值 与 下一个节点的词频值是否是邻近数字
                if(bucket.cnt == bucket.next.cnt - 1){
                    map.put(key, bucket.next);
                    bucket.next.strSet.add(key);
                }else {
                    Bucket newBucket = new Bucket(key, bucket.cnt + 1);
                    map.put(key, newBucket);
                    insert(bucket, newBucket);
                }
                // 当前bucket的存储字符串的set集合要删除为key值的字符串记录
                bucket.strSet.remove(key);
                // 删除后，如果这个桶的set集合为空，则从双向链表中删除这个节点
                if(bucket.strSet.isEmpty()){
                    remove(bucket);
                }
            }
        }

        // 测试用例保证：在每次调用 dec 时，数据结构中总存在 key
        public void dec(String key) {
            // 取出其bucket节点
            Bucket bucket = map.get(key);
            // 如果当前key的词频为1时
            if(bucket.cnt == 1){
                map.remove(key);
            }else {
                // // 判断当前bucket节点的词频值 与 上一个节点的词频值是否是邻近数字
                if(bucket.cnt == bucket.last.cnt + 1){
                    map.put(key, bucket.last);
                    bucket.last.strSet.add(key);
                }else {
                    Bucket newBucket = new Bucket(key, bucket.cnt - 1);
                    map.put(key, newBucket);
                    insert(bucket.last, newBucket);
                }
            }
            /// 当前bucket的存储字符串的set集合要删除为key值的字符串记录
            bucket.strSet.remove(key);
            // 删除后，如果这个桶的set集合为空，则从双向链表中删除这个节点
            if(bucket.strSet.isEmpty()){
                remove(bucket);
            }
        }

        // 返回任意一个计数最大的字符串
        public String getMaxKey() {
            return tail.last.strSet.iterator().next();
        }

        // 返回任意一个计数最小的字符串
        public String getMinKey() {
            return head.next.strSet.iterator().next();
        }
    }
}
